You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

這題和 198. House Robber (Medium) 差不多但不同的點在於現在房子變成循環的，也就是說如果偷了第一間那麼最後一間也不能偷，同理最後一間偷了則第一間不能偷。

Step

因為偷了第一間（從第一間開始）就不能偷最後一間，所以將最後一間移除掉並和 198. House Robber (Medium) 一樣建立 移除掉最後一間房子 的 dp array

接著建立第二個 dp 是從略過第一間，如果略過第一間就可以偷到最後一間（從第二間開始），所以移除掉第一間並和198. House Robber (Medium) 一樣建立 移除掉第一間房子 的 dp array

Create skipLastHouseDp

1. nums = [2] 則只有一個選項便是 2
   

2. nums = [2,7] 則有兩個選項，第一個是去第一間拿到 1 塊第二個是去第二間拿到 7 塊，而 7 > 1 則將 7 放入 skipLastHouseDp 中代表 nums = [2,7] 時可以拿到最多的錢。
   

3. nums = [2,7,9] 有兩個選項
   • 拿 9 和 7 之前的房子中最多錢的，因為 7 連著 9 所以要跳過 7 找 7 之前的最大值
     
   • 不拿 9 而拿 9 之前的房子中最多錢的，而 9 之前最多錢的在 2 (nums = [2,7]) 已經算過並放進 dp 裡面了
     
   • 方法一和方法二的最大值放入 dp 中表示 nums = [2,7,9] 時可以拿得最多錢
     

4. nums = [2,7,9,3] 有兩個選項
   • 拿 3 和 9 之前的房子 [2,7] 中最多錢的值相加，因為 9 連著 3 所以要跳過 9 找 9 之前的最大值，而 9 之前的最大值在 2 (nums = [2,7]) 已經算過並放進 dp 裡了
     
   • 不拿 3 而拿 3 之前的房子 [2,7,9] 中最多錢的，而 3 之前最多錢的已經在 3 (nums = [2,7,9]) 中算過並放進 dp 中了
     
   • 方法一和方法二的最大值放入 dp 中表示 nums = [2,7,9,3] 時可以拿得最多錢
     

Create skipFirstHouseDp

1. 因為要略過第一間房子，所以要從第二間房子開始，而略過第一間房子所以 skipFirstHouseDp 也從 index = 2 開始。
   

2. nums = [7] 則只有一個選項便是 7
   

3. nums = [7,9] 則有兩個選項，第一個是去第一間拿到 7 塊第二個是去第二間拿到 9 塊，而 9 > 7 則將 9 放入 skipFirstHouseDp 中代表 nums = [7,9] 時可以拿到最多的錢。
   

4. nums = [7,9,3] 有兩個選項
   • 拿 3 和 9 之前的房子中最多錢相加，因為 9 連著 3 所以要跳過 9 找 9 之前的最大值
     
   • 不拿 3 而拿 3 之前的房子中最多錢的，而 3 之前最多錢的在 3 (nums = [7,9]) 已經算過並放進 dp 裡面了
     
   • 方法一和方法二的最大值放入 dp 中表示 nums = [7,9,3] 時可以拿得最多錢
     

5. nums = [7,9,3,1] 有兩個選項
   • 拿 1 和 3 之前的房子中最多錢相加，因為 3 連著 1 所以要跳過 3 找 3 之前的最大值，而 nums = [7,9] 在 3 已經算過並放進 skipFirstHouseDp 中了
     
   • 不拿 1 而拿 1 之前的房子中最多錢的，而 1 之前最多錢的在 4 (nums = [7,9,3]) 已經算過並放進 dp 裡面了
     
   • 方法一和方法二的最大值放入 dp 中表示 nums = [7,9,3,1] 時可以拿得最多錢
     

Answer

比較 skipLastHouseDp 和 skipFirstHouseDp 中最大值便是解答。

Coding

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    if (nums.length === 1) return nums[0];
    if (nums.length === 2) return Math.max(nums[0], nums[1]);

    const skipLastHouse = [];
    skipLastHouse[0] = nums[0];
    skipLastHouse[1] = Math.max(nums[0], nums[1]);
    for(let i = 2; i < nums.length - 1; i++) {
        skipLastHouse[i] = Math.max(nums[i] + skipLastHouse[i - 2], skipLastHouse[i - 1]);
    }

    const skipFirstHouse = [];
    skipFirstHouse[1] = nums[1];
    skipFirstHouse[2] = Math.max(nums[1], nums[2]);
    for(let i = 3; i < nums.length; i++) {
        skipFirstHouse[i] = Math.max(nums[i] + skipFirstHouse[i - 2], skipFirstHouse[i - 1]);
    }

    return Math.max(skipLastHouse[skipLastHouse.length - 1], skipFirstHouse[skipFirstHouse.length - 1]);
};

Time complexity: O(n)